﻿#define _CRT_SECURE_NO_WARNINGS 1
//二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/bianry-number-to-string-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//#define MAX_LEN 32
//char* printBin(double num){
//	if (num<0 || num>1)
//	{
//		return "ERROR";
//	}
//	char* res = (char*)calloc(MAX_LEN + 1, sizeof(char));
//	res[0] = '0';
//	res[1] = '.';
//	int id = 2;
//	double tmp = num;
//	while (id<MAX_LEN&&tmp != 0)
//	{
//		res[id++] = (int)(tmp * 2) + '0';
//		if (tmp * 2 >= 1)
//		{
//			tmp = tmp * 2 - 1;
//		}
//		else
//		{
//			tmp = tmp * 2;
//		}
//	}
//	if (tmp != 0)
//	{
//		return "ERROR";
//	}
//	return res;
//}








/**绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。

给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数 y。返回绘制过后的数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/draw-line-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* drawLine(int length, int w, int x1, int x2, int y, int* returnSize){
//	*returnSize = length;
//	if ((y + 1)>(32 * length / w))
//	{
//		return NULL;
//	}
//	int *res = (int*)calloc(length, sizeof(int));
//	int row = y*w / 32;
//	for (int i = x1; i <= x2; i++)
//	{
//		unsigned int tmp = (unsigned int)1 << (31 - (i % 32));
//		res[i / 32 + row] += tmp;
//	}
//	return res;
//}








//递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
//int multiply(int A, int B){
//	if (A == 0 || B == 0)
//	{
//		return 0;
//	}
//	if (A>B)
//	{
//		return A + multiply(A, B - 1);
//	}
//	return B + multiply(A - 1, B);
//}








//给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
//
//不占用额外内存空间能否做到？
//
//
//void rotate(int** matrix, int matrixSize, int* matrixColSize){
//	for (int i = 0; i<matrixSize / 2; i++)
//	{
//		for (int j = 0; j<(matrixSize + 1) / 2; j++)
//		{
//			int tmp = matrix[i][j];
//			matrix[i][j] = matrix[matrixSize - j - 1][i];
//			matrix[matrixSize - j - 1][i] = matrix[matrixSize - i - 1][matrixSize - j - 1];
//			matrix[matrixSize - i - 1][matrixSize - j - 1] = matrix[j][matrixSize - i - 1];
//			matrix[j][matrixSize - i - 1] = tmp;
//		}
//	}
//	return matrix;
//}








//编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
//void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
//	int m = matrixSize;
//	int n = matrixColSize[0];
//	int row[m];
//	int col[n];
//	memset(row, 0, sizeof(row));
//	memset(col, 0, sizeof(col));
//	for (int i = 0; i<m; i++)
//	{
//		for (int j = 0; j<n; j++)
//		{
//			if (matrix[i][j] == 0)
//			{
//				row[i] = col[j] = true;
//			}
//		}
//	}
//	for (int i = 0; i<m; i++)
//	{
//		for (int j = 0; j<n; j++)
//		{
//			if (row[i] || col[j])
//			{
//				matrix[i][j] = 0;
//			}
//		}
//	}
//	return matrix;
//}








/**下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例1:
* Note: The returned array must be malloced, assume caller calls free().
*/
//int cntbit(long n)
//{
//	int count = 0;
//	while (n>0)
//	{
//		if (n & 1)
//		{
//			count++;
//		}
//		n = n >> 1;
//	}
//	return count;
//}
//int* findClosedNumbers(int num, int* returnSize){
//	int* a = malloc(sizeof(int) * 2);
//	*returnSize = 2;
//	a[0] = a[1] = -1;
//	int bit = cntbit(num);
//	long n = 0;
//	if (num == 2147483647)
//	{
//		return a;
//	}
//	else if (num<2147483647)
//	{
//		for (n = num + 1; n <= 2147483647; n++)
//		{
//			if (cntbit(n) == bit)
//			{
//				a[0] = n;
//				break;
//			}
//		}
//		for (n = num - 1; n >= 0; n--)
//		{
//			if (cntbit(n) == bit)
//			{
//				a[1] = n;
//				break;
//			}
//		}
//	}
//	return a;
//}







//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//
//你可以假设数组中无重复元素。
//int searchInsert(int* nums, int numsSize, int target){
//	int i = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i] >= target)
//		{
//			return i;
//		}
//	}
//	return i;
//}








//你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
//
//假设你有 n 个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
//
//你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/first-bad-version
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//// The API isBadVersion is defined for you.
//// bool isBadVersion(int version);
//
//int firstBadVersion(int n) {
//	int l = 0;
//	int r = n;
//	while (l<r)
//	{
//		int m = l + (r - l) / 2;
//		if (isBadVersion(m))
//		{
//			r = m;
//		}
//		else
//		{
//			l = m + 1;
//		}
//	}
//	return r;
//}








/**有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

* 解码
* @param nums string字符串 数字串
* @return int整型
*/
//int solve(char* nums) {
//	// write code here
//	if (!nums)
//	{
//		return 0;
//	}
//	int res = 1;
//	int a = 0;
//	int b = 0;
//	int tmp = 0;
//	char last = 0;
//	char ch = 0;
//	while (ch = *nums++)
//	{
//		if (ch<'3')
//		{
//			if (ch == '0')
//			{
//				return 0;
//			}
//			a = b = res;
//			last = ch;
//			while (ch = *nums++)
//			{
//				if (ch == '1' || ch == '2')
//				{
//					tmp = b;
//					b += a;
//					a = tmp;
//					last = ch;
//					continue;
//				}
//				if (ch == '0')
//				{
//					b = a;
//					break;
//				}
//				if (ch<'7' || last == '1')
//				{
//					b += a;
//				}
//				break;
//			}
//			res = b;
//			if (!ch)
//			{
//				break;
//			}
//		}
//	}
//	return res;
//}






//
//如果一个数列S满足对于所有的合法的i, 都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零, 我们就称数列S为等差数列。
//小易现在有一个长度为n的数列x, 小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作, 并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列, 小易需要判别一个数列是否能通过交换操作变成等差数列
//#include <stdio.h>
//#include <stdlib.h>
//int cmp(const void* a, const void* b)
//{
//	return *(int*)a - *(int*)b;
//}
//int main()
//{
//	int n, i, d, x;
//	int a[50];
//	scanf("%d", &n);
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", a + i);
//	}
//	qsort(a, n, sizeof(int), cmp);
//	d = a[1] - a[0];
//	for (i = 2; i<n; i++)
//	{
//		x = a[i] - a[i - 1];
//		if (x != d)
//		{
//			printf("Impossible\n");
//			break;
//		}
//	}
//	if (i >= n)
//	{
//		printf("Possible\n");
//	}
//	return 0;
//}